package 力扣._00周赛._368周赛.问题3;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        //组内元素的最大数量由，重复值的最小个数决定
        int min = Integer.MAX_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) map.put(num, map.get(num) + 1);
            else map.put(num, 1);
        }
        Set<Integer> set = map.keySet();
        for (Integer i : set) {
            min = Math.min(min, map.get(i));
        }
        //下标最小数量，由min下降
        for (int mod = min; mod >= 1; mod--) {
            int sum = 0;
            boolean isok = true;
            for (Integer key : set) {
                int c = map.get(key);
                int i;
                for (i = c / (mod + 1); i >= 0; i--) {
                    if ((c - i * (mod + 1)) % mod == 0) {
                        sum += i + (c - i * (mod + 1)) / mod;
                        break;
                    }
                }
                if (i == -1) {
                    isok = false;
                    break;
                }
            }
            if (isok) return sum;
        }
        return nums.length;

    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,3,1,1,3};
        int i = new Solution().minGroupsForValidAssignment(nums);
        System.out.println(i);

    }
}
